package com.darwin.darwinIsometric.pathfinding.expand
{
	
	import com.darwin.darwinIsometric.pathfinding.ANode;
	import com.darwin.darwinIsometric.pathfinding.AStar;
	import com.darwin.darwinIsometric.pathfinding.MapGrid;
	
	import flash.display.DisplayObject;
	import flash.display.Shape;
	import flash.events.Event;
	import flash.events.EventDispatcher;
	import flash.geom.Point;
	import flash.utils.Dictionary;
	import flash.utils.getTimer;
	
	[Event(name="walkerPathChange",type="com.darwin.darwinIsometric.pathfinding.expand.WalkManagerEvent")]

	/**
	 * 寻路中的动态碰撞管理扩展类
	 * <li>如果你希望运动物体在寻路时实现碰撞检测,并自动绕开其他运动物体, 则可以考虑使用此扩展类来管理寻路和运动过程</li>
	 * @author Roland
	 * 
	 */
	public class WalkManager extends EventDispatcher
	{
		/**
		 *	最大支持的行动单位占格数 
		 */
		public static var MAX_WALKER_SIZE:int = 4;
		
		/**
		 *	当遇到追撞时单位停止等待的步数 
		 */
		public static var WAITING_STEP:int = 2;
		/**
		 *	一帧中最大允许耗费的时间(ms)
		 */
		public static const MAX_FRAME_TIME:int = 300;
		private var _gridList:Vector.<MapGrid>;//地图列表，_gridList[0]放1x1寻路地图，_gridList[1]放2x2寻路地图,依次类推
		private var _orgGridList:Vector.<MapGrid>;//原始地图数据列表,用于恢复动态物体覆盖的walkable
		private var _astar:AStar;
		private var _walkerDic:Dictionary;
		private var _frameTime:int = 0;
		private var _frameShape:Shape;
		/**
		 *	实例化一个运动管理器 
		 * @param astar a*算法实例
		 * @param grid 地图数据
		 * 
		 */
		public function WalkManager(astar:AStar,grid:MapGrid)
		{
			_astar = astar;
			_walkerDic = new Dictionary();
			_gridList = new Vector.<MapGrid>();
			_orgGridList = new Vector.<MapGrid>();
			_frameShape  = new Shape();
			
			updateMapGrid(grid);
			
			_frameShape.addEventListener(Event.ENTER_FRAME,render);
		}
		
		/**
		 *	处理 
		 * @param event
		 * 
		 */
		private function render(event:Event):void
		{
//			trace(usedTime);
			//记录帧时间
			_frameTime = getTimer();
		}
		
		/**
		 * 更新地图数据
		 * <br/>offsetX和offsetY属性提供给无限地图寻路解决9屏地图数据移动导致的单位定位问题
		 * @param grid
		 * @param offsetX 移动单位偏移值及其路径偏移值x
		 * @param offsetY 移动单位偏移值及其路径偏移值y
		 */
		public function updateMapGrid(grid:MapGrid,offsetX:int = 0,offsetY:int = 0):void
		{
			var i:int;
			var $grid:MapGrid = grid.clone();
			for (i = 0; i < MAX_WALKER_SIZE; i++) 
			{
				_gridList[i] = toNxN($grid,i+1);
				_orgGridList[i] = _gridList[i].clone();
			}
			for each (var walker:Walker in _walkerDic) 
			{
				walker.x += offsetX;
				walker.y += offsetY;
				var path:Array = walker.path;
				for (i = 0; i < path.length; i++) 
				{
					path[i].x += offsetX;
					path[i].y += offsetY;
				}
				setWalkableByWalker(walker);
			}
		}
		
		/**
		 *	添加运动单位 
		 * @param walkerId 单位id，应保持全局唯一
		 * @param posX 单位当前所在网格位置x
		 * @param posY 单位当前所在网格位置y
		 * @param size 单位大小 size*size
		 * @param autoRedirect 遇到其他行动物体后是否自动重定向，如果此项为false，此walker将完全按照既定路径行
		 * 走，即使遇到其他行动物体也将不做反映，此类walker将完全通过setPath方法从外部进行控制路径或通过setEndPos进行普通a*寻路。
		 */
		public function addWalker(walkerId:String,posX:int,posY:int,size:int = 1,autoRedirect:Boolean = true):void
		{
			var $walker:Walker = new Walker(walkerId,posX,posY,size,null,autoRedirect);
			setWalkableByWalker($walker);
			_walkerDic[walkerId] = $walker;
		}
		
		/**
		 *	移除运动单位 
		 * @param walkerId 单位id
		 * 
		 */
		public function removeWalker(walkerId:String):void
		{
			var $walker:Walker = _walkerDic[walkerId];
			recoverWalkableByWalker($walker);
			delete _walkerDic[walkerId];
		}
		
		/**
		 *	直接将某个运动单位的当前位置，此动作将清除运动单位的现有路径。
		 * @param walkerId
		 * @param posX
		 * @param posY
		 * 
		 */
		public function setPos(walkerId:String,posX:int,posY:int):void
		{
			var $walker:Walker = _walkerDic[walkerId];
			recoverWalkableByWalker($walker);
			$walker.x = posX;
			$walker.y = posY;
			$walker.path = [];
			setWalkableByWalker($walker);
		}
		
		/**
		 *	设置某行走单位终点 
		 * @param walkerId 行走单位id
		 * @param endPosX 终点x
		 * @param endPosY 终点y
		 * @param needRecover 是否需要恢复walkable,外部调用请始终保持此参数为true
		 * @param ignoreWorker 行走时是否其他所有运动单位(通常用来防止被卡)
		 * @param pathTrun 将路径从终点开始截去的点的个数,例如传了3,则返回的路径将是完整路径截取最后3个点之后的路径
		 * @return 是否能找到走到终点的路
		 * 
		 */
		public function setEndPos(walkerId:String,endPosX:int,endPosY:int,needRecover:Boolean = true,ignoreWorker:Boolean = false,pathTrun:uint = 0):Boolean
		{
			var $walker:Walker = _walkerDic[walkerId];
			var $gSize:int = $walker.size -1;
			var $grid:MapGrid = _gridList[$gSize];
			var $orgGrid:MapGrid = _orgGridList[$gSize];
			if(needRecover)
			{
				recoverWalkableByWalker($walker);
			}
			var otherWalker:Walker;
			if(ignoreWorker)
			{
				for each (otherWalker in _walkerDic) 
				{
					recoverWalkableByWalker(otherWalker);
				}
			}

			var $result:Boolean;
			$grid.setStartNode($walker.x,$walker.y);
			$grid.setEndNode(endPosX,endPosY);
			
			var time:int = getTimer();
			$result = _astar.findPath($grid);
			time = getTimer() - time;
			
			if(needRecover)
			{
				setWalkableByWalker($walker);
			}
			if(ignoreWorker)
			{
				for each (otherWalker in _walkerDic) 
				{
					setWalkableByWalker(otherWalker);
				}
			}
			
			if($result)
			{
//				trace(time + "ms 路径长度:" + _astar.path.length);
				$walker.path = _astar.path;
				if(pathTrun>0)
				{
					var $index:int = $walker.path.length - pathTrun > 0 ? $walker.path.length - pathTrun : 0;
					$walker.path.splice($index);
				}
			}else{
				trace( time + "ms 路径未找到");
				$walker.path = [];
			}
			var $e:WalkManagerEvent = new WalkManagerEvent(WalkManagerEvent.WALKER_PATH_CHANGE);
			$e.walkerId = walkerId;
			$e.path = $walker.path;
			dispatchEvent($e);
			return $result;
		}
		
		/**
		 *	直接替换某行动物体当前路径 
		 * @param walkerId 行动物体id
		 * @param path 路径
		 * @param dispatchEvent 是否触发路径改变事件
		 */
		public function setPath(walkerId:String,path:Array,dispatchEvent:Boolean =false):void
		{
			if(_walkerDic[walkerId] != null)
			{
				var $walker:Walker = _walkerDic[walkerId];
				$walker.path = path;
			}
			if(dispatchEvent)
			{
				dispatchPathChangeEvent(walkerId);
			}
		}
		
		/**
		 *	请求将某个单位移动到下一步 
		 * @param walkerId 单位id
		 * @return 移动后的新位置
		 */
		public function goNextStep(walkerId:String):Object
		{
			var $walkerA:Walker = _walkerDic[walkerId];
			var $grid:MapGrid = _gridList[$walkerA.size-1];
			var $orgGrid:MapGrid = _orgGridList[$walkerA.size-1];
			var $gSize:int = $walkerA.size-1;
			
			var $moveEnd:Boolean;//是否已到终点
			if($walkerA.path.length<=0){
				$moveEnd = true;
			}else{
				$moveEnd = false;
				var $hit:Boolean = false;
				var $next:Object = $walkerA.path.shift();
				$walkerA.angle = getAngle($walkerA.x,$walkerA.y,$next.x,$next.y);
				//消除自己占格
				recoverWalkableByWalker($walkerA);
				if($walkerA.autoRedirect == true)
				{
					for (var id:String in _walkerDic) 
					{
						if(id != walkerId)//不考虑自己
						{
							var $walkerB:Walker = _walkerDic[id];
							var $isHit:Boolean = blockHitTest($next.x,$next.y,$walkerA.size,$walkerB.x,$walkerB.y,$walkerB.size);//是否碰撞
							var $end:Object;
							if($isHit)//如果撞了
							{
								var $dAngle:int = getDifAngle($walkerA,$walkerB);
//															trace("碰撞角度",$dAngle);
								if(($dAngle >= 90 || $walkerB.isWaiting) && usedTime < MAX_FRAME_TIME)//(正撞或者B静止)且未到达处理上限
								{	//A绕
									$end = $walkerA.path[$walkerA.path.length-1];
									if($end)
									{
										setEndPos(walkerId,$end.x,$end.y,false);
									}else{//终点
										$moveEnd = true;//停下
									}
								}else{//追撞
									if($walkerA.isWaiting)//如果已经等待过了
									{//重新寻路
										$end = $walkerA.path[$walkerA.path.length-1];
										if($end)
										{
											setEndPos(walkerId,$end.x,$end.y,false);
										}else{//终点
											$moveEnd = true;//停下
										}
									}else{
										//等待
										for (var i:int = 0; i < WAITING_STEP; i++) 
										{
											$walkerA.path.unshift({"x":$next.x,"y":$next.y});
										}
										dispatchPathChangeEvent($walkerA.id);
									}
								}
								$hit = true;
								break;
							}
						}
					}
				}

				
				if($hit==false)
				{
					$walkerA.x = $next.x;
					$walkerA.y = $next.y;
				}
				//设置占格
				setWalkableByWalker($walkerA);
			}

			return {"x":$walkerA.x,"y":$walkerA.y,"moveEnd":$moveEnd , "hit":$hit};
		}
		
		/**
		 *	获得某行动单位当前路径的终点位置 
		 * @param walkerId
		 * @return {"x":...,"y":...}
		 * 
		 */
		public function getEndPos(walkerId:String):Object
		{
			var $walker:Walker = _walkerDic[walkerId];
			var $moveEnd:Boolean = $walker.path.length <= 0 ? true : false;
			var $endX:int;
			var $endY:int;
			if($moveEnd == false)
			{
				$endX = $walker.path[$walker.path.length-1].x;
				$endY = $walker.path[$walker.path.length-1].y;
			}else{
				$endX = $walker.x;
				$endY = $walker.y;
			}
			return {"x":$endX,"y":$endY,"moveEnd":$moveEnd};
		}
		
		/**
		 *	获取某移动单位当前的位置 
		 * @param walkerId
		 * @return 
		 * 
		 */
		public function getCurruntPos(walkerId:String):Object
		{
			var $walker:Walker = _walkerDic[walkerId];
			var $moveEnd:Boolean = $walker.path.length <= 0 ? true : false;
			return {"x":$walker.x,"y":$walker.y,"moveEnd":$moveEnd};
		}
		
		public function getGrid(size:int = 1):MapGrid
		{
			return _gridList[size-1];
		}
		
		/**
		 *	发布路径改变事件 
		 * @param walkerId
		 * 
		 */
		private function dispatchPathChangeEvent(walkerId:String):void
		{
			var $walker:Walker = _walkerDic[walkerId];
			if($walker)
			{
				var $e:WalkManagerEvent = new WalkManagerEvent(WalkManagerEvent.WALKER_PATH_CHANGE);
				$e.walkerId = $walker.id;
				$e.path = $walker.path;
				dispatchEvent($e);
			}
		}
		
		/**
		 *	当前帧已经耗费的时间 
		 * @return 
		 * 
		 */
		private function get usedTime():int
		{
			return getTimer() - _frameTime;
		}
		
		/**
		 *	设置一个walker在所有NxN地图的walkable数据 
		 * @param walker
		 * 
		 */
		private function setWalkableByWalker(walker:Walker,walkable:int = 0):void
		{
			for (var i:int = 0; i < MAX_WALKER_SIZE; i++) 
			{
				var $gSize:int = i;
				var $grid:MapGrid = _gridList[$gSize];
				var $orgGrid:MapGrid = _orgGridList[$gSize];
				setBlockMark($grid,walker.id,walker.x-$gSize,walker.y-$gSize,walker.size+$gSize);
				setBlockWalkable($grid,walkable,walker.x-$gSize,walker.y-$gSize,walker.size+$gSize);
			}
		}
		
		/**
		 *	从源数据恢复一个walker的所有NxN地图walkable数据
		 */
		private function recoverWalkableByWalker(walker:Walker):void
		{
			for (var i:int = 0; i < MAX_WALKER_SIZE; i++) 
			{
				var $gSize:int = i;
				var $grid:MapGrid = _gridList[$gSize];
				var $orgGrid:MapGrid = _orgGridList[$gSize];
				removeBlockMark($grid,walker.id,walker.x-$gSize,walker.y-$gSize,walker.size+$gSize);
				copyBlockWalkableByMark($orgGrid,$grid,walker.x-$gSize,walker.y-$gSize,walker.size+$gSize);
			}
		}
		
		/**
		 * 消除正方形区域的格子的某种标记 (从标记列表删除)
		 * @param grid 要修改的地图数据
		 * @param mark 要消除的标记
		 * @param x 坐标x
		 * @param y 坐标y 
		 * @param size 区域体积
		 * 
		 */
		private static function removeBlockMark(grid:MapGrid,mark:String,x:int,y:int,size:int):void
		{
			for (var $y:int = y; $y < y+size; $y++) 
			{
				for (var $x:int = x; $x < x+size; $x++) 
				{
					if($x < 0 || $y < 0 || $x >= grid.numCols || $y >= grid.numRows)continue;
					var node:ANode = grid.getNode($x,$y);
					if(node.marks == null)continue;
					var index:int = node.marks.indexOf(mark);
					if(index >= 0)node.marks.splice(index,1);
				}
			}
		} 
		
		/**
		 *	给一个正方形区域的格子设置标记 (推入标记列表)
		 * @param grid 要修改的地图数据
		 * @param mark 要设置的标记
		 * @param x 坐标x
		 * @param y 坐标y 
		 * @param size 区域体积
		 * 
		 */
		private static function setBlockMark(grid:MapGrid,mark:String,x:int,y:int,size:int):void
		{
			for (var $y:int = y; $y < y+size; $y++) 
			{
				for (var $x:int = x; $x < x+size; $x++) 
				{
					if($x < 0 || $y < 0 || $x >= grid.numCols || $y >= grid.numRows)continue;
					var node:ANode = grid.getNode($x,$y);
					if(node.marks == null)node.marks = [];
					if(node.marks.indexOf(mark) == -1) node.marks.push(mark);
				}
			}
		}
		
		/**
		 *	从一张地图中向另一张地图拷贝一个正方形区域的walkable(只有目标地图的node里mark为null或[]时,数据才会被拷贝)
		 * @param from walkable来源地图
		 * @param to 要拷贝到的地图
		 * @param x 位置x
		 * @param y 位置y
		 * @param size 区域大小
		 * 
		 */
		private static function copyBlockWalkableByMark(from:MapGrid,to:MapGrid,x:int,y:int,size:int):void
		{
			for (var $y:int = y; $y < y+size; $y++) 
			{
				for (var $x:int = x; $x < x+size; $x++) 
				{
					if($x < 0 || $y <0 || $x >= from.numCols || $y >= from.numRows) continue;
					var targetNode:ANode = to.getNode($x,$y);
					if(targetNode.marks == null || targetNode.marks.length == 0)
					{
						to.setWalkable($x,$y,from.getWalkable($x,$y));
					}
				}
			}
		}
		
		/**
		 *	给一个正方形区域设置walkable 
		 * @param grid 要修改的地图数据
		 * @param walkable 要设置的walkable
		 * @param x 坐标x
		 * @param y 坐标y 
		 * @param size 区域体积
		 * 
		 */
		private static function setBlockWalkable(grid:MapGrid,walkable:int,x:int,y:int,size:int):void
		{
			for (var $y:int = y; $y < y+size; $y++) 
			{
				for (var $x:int = x; $x < x+size; $x++) 
				{
					if($x < 0 || $y < 0 || $x >= grid.numCols || $y >= grid.numRows)continue;
					grid.setWalkable($x,$y,walkable);
				}
			}
		}
		
		/**
		 *	判断两个正方形区域是否相叠 
		 * @param ax 区域a坐标x
		 * @param ay 区域a坐标y
		 * @param asize 区域a尺寸
		 * @param bx 区域b坐标x
		 * @param by 区域b坐标y
		 * @param bsize 区域b尺寸
		 * @return 
		 * 
		 */
		private static function blockHitTest(ax:int,ay:int,asize:int,bx:int,by:int,bsize:int):Boolean
		{
//			return ax==bx && ay==by;
			var xInner:Boolean = false;
			var yInner:Boolean = false;
			if( (bx >= ax && (bx-ax)<asize) || (ax > bx && (ax-bx)<bsize))
			{
				xInner = true;
			}
			if((by >= ay && (by-ay)<asize) || (ay > by && (ay-by)<bsize) )
			{
				yInner = true;
			}
			if(xInner && yInner)
			{
				return true;
			}
			return false;
		}
		
		/**
		 *	获取a与b行走方向的正夹角
		 * @param a
		 * @param b
		 * @return 
		 * 
		 */
		private static function getDifAngle(a:Walker,b:Walker):int
		{
			var dAngle:int = Math.abs(b.angle - a.angle);
			if(dAngle>180){
				dAngle = 360 - dAngle;
			}
			return dAngle;
		}
		
		private static function getAngle(x0:int,y0:int,x1:int,y1:int):int
		{
			var dest:Number = (x1-x0)/Math.sqrt((y1-y0)*(y1-y0)+ (x1-x0)*(x1-x0));
//			trace(dest);
			var angle:Number;
			if((y0-y1) > 0)
			{
				angle = Math.asin(dest)*180/Math.PI; //+ (quadrant-1)*90;
			}else{
				angle = 180-Math.asin(dest)*180/Math.PI;
			}
			if(angle<0)angle = 270-angle;
			return int(angle);
		}

		/**
		 *	 根据传入的地图数据，返回一张合适NxN物件寻路的新地图
		 * @param map
		 * @param N 寻路物件的格数，2表示2x2
		 */
		public static function toNxN(map:MapGrid,N:int):MapGrid
		{
			if(map.enlargeValue == N)return map;
			var $map:MapGrid = map.clone();
			var i:int;
			var j:int;
			var numCols:int = $map.numCols;
			var numRows:int = $map.numRows;
			var walkableValue:int =  N*2*100000;
			for(i = 0;i<numCols;i++)
			{
				for(j = 0;j<numRows;j++)
				{
					if($map.getWalkable(i,j) != 0)
					{
						if(i < 0 || j<0 || i> numCols || j> numRows)
						{
							$map.setWalkable(i,j,walkableValue);
						}else{
							var $w:int = 1;
							for(var m:int = 0;m<N;m++)
							{
								for(var n:int = 0;n<N;n++)
								{
									if((i+m) <= 0 || (j+n)<=0 || (i+m)>= numCols || (j+n)>= numRows)
									{
										continue;
									}
									if($map.getWalkable(i+m,j+n) == 0)
									{
										$w = 0;
										break;
									}
								}
								if($w == 0) break;
							}//for
							if($w == 0)
							{
								$map.setWalkable(i,j,walkableValue);
							}
						}//if
					}//if
				}//for
			}//for
			
			for(i = 0;i<numCols;i++)
			{
				for(j=0;j<numRows;j++)
				{
					if($map.getWalkable(i,j) == walkableValue)
					{
						$map.setWalkable(i,j,0);
					}
				}
			}
			$map.enlargeValue = N;
			return $map;
		}
		
	}
}
class Walker{
	private var _id:String;
	private var _x:int;
	private var _y:int;
	private var _angle:int;
	private var _path:Array;
	private var _size:int;
	private var _autoRedirect:Boolean;
	/**
	 *	实例化一个行走单位 
	 * @param id 单位id
	 * @param x 单位当前所在网格位置x 
	 * @param y 单位当前所在网格位置y
	 * @param size 单位占格
	 * @param path 单位行走路径
	 * @param autoRedirect 单位遇到障碍是否自动重定向
	 */
	public function Walker(id:String,x:int,y:int,size:int = 1,path:Array = null,autoRedirect:Boolean = true)
	{
		_id = id;
		_x = x;
		_y = y;
		_size = size;
		_path = path ? path : [];
		_angle = 0;
		_autoRedirect = autoRedirect;
	}

	/**
	 *	单位id 
	 */
	public function get id():String
	{
		return _id;
	}

	/**
	 * @private
	 */
	public function set id(value:String):void
	{
		_id = value;
	}

	/**
	 *	单位当前所在网格位置x 
	 */
	public function get x():int
	{
		return _x;
	}

	/**
	 * @private
	 */
	public function set x(value:int):void
	{
		_x = value;
	}

	/**
	 *  单位当前所在网格位置y
	 */
	public function get y():int
	{
		return _y;
	}

	/**
	 * @private
	 */
	public function set y(value:int):void
	{
		_y = value;
	}

	/**
	 *	 单位行走路径
	 */
	public function get path():Array
	{
		return _path;
	}

	/**
	 * @private
	 */
	public function set path(value:Array):void
	{
		_path = value;
	}

	/**
	 * 单位面朝的方向 
	 */
	public function get angle():int
	{
		return _angle;
	}

	/**
	 * @private
	 */
	public function set angle(value:int):void
	{
		_angle = value;
	}

	/**
	 *	单位占格 
	 */
	public function get size():int
	{
		return _size;
	}

	/**
	 * @private
	 */
	public function set size(value:int):void
	{
		_size = value;
	}
	
	/**
	 *	移动单位是否处于停止等待的状态,(不一定是走到了终点,只要下一步和当前位置处于同一格即判断为等待) 
	 * @return 
	 * 
	 */
	public function get isWaiting():Boolean
	{
		if(_path.length == 0)
		{
			return true;
		}
		else if(_x == _path[0].x && _y == _path[0].y)
		{
			return true;
		}
		else if(_path.length > 1 &&_path[0].x  == _path[1].x && _path[0].y == _path[1].y)
		{
			return true;
		}
		return false;
	}

	/**
	 *	单位遇到障碍是否自动重定向 
	 */
	public function get autoRedirect():Boolean
	{
		return _autoRedirect;
	}
}